#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
#http://www.careercup.com/question?id=14851686
#Facebook interview question

from utils import *

def find_non_adjacent_sub_sequence(arr):
    if not arr: return (0, )
    if len(arr) == 1: return (1, arr[0])
    last_index, max_sum, max_sum_sequence = [], 0, []
    max_sum_index = -1

    for i in range(0, len(arr)):
        if i <= 1:
            last_index.append(-1)
            max_sum_sequence.append(arr[i])
        elif i == 2:
            last_index.append(0)
            max_sum_sequence.append(arr[i] + arr[0])
        else:
            if max_sum_sequence[i - 2] > max_sum_sequence[i - 3]:
                last_index.append(i - 2)
                max_sum_sequence.append(arr[i] + max_sum_sequence[i - 2])
            else:
                last_index.append(i - 3)
                max_sum_sequence.append(arr[i] + max_sum_sequence[i - 3])
        if max_sum_sequence[i] > max_sum:
            max_sum, max_sum_index = max_sum_sequence[i], i

    return max_sum, find_sub_sequence(arr, last_index, max_sum_index)


def find_sub_sequence(arr, last_index, index):
    result = []
    while index != -1:
        result.append(index)
        index = last_index[index]
    result.reverse()
    return result


if __name__ == "__main__":
    for i in range(0, 20):
        arr = random_arr()
        print find_non_adjacent_sub_sequence(arr)
